package com.yequan.leetcode.tree.inordertraversal_94;

import com.yequan.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的中序遍历
 *
 * @author : Administrator
 * @date : 2020/3/25
 */
public class RecodeInorderTraversal {


    /**
     * 递归法:
     * 先访问左子树,后访问根节点,最后右子树
     */
    class Factorial {

        public List<Integer> inorderTraversal1(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper1(root, res);
            return res;
        }

        private void helper1(TreeNode root, List<Integer> res) {
            if (null != root) {
                if (null != root.left) {
                    helper1(root.left, res);
                }
                res.add(root.val);
                if (null != root.right) {
                    helper1(root.right, res);
                }
            }
        }

        public List<Integer> inorderTraversal2(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper2(root, res);
            return res;
        }

        private void helper2(TreeNode root, List<Integer> res) {
            if (null != root) {
                if (null != root.left) {
                    helper2(root.left, res);
                }
                res.add(root.val);
                if (null != root.right) {
                    helper2(root.right, res);
                }
            }
        }

        public List<Integer> inorderTraversal3(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper3(root, res);
            return res;
        }

        private void helper3(TreeNode root, List<Integer> res) {
            if (null != root) {
                if (null != root.left) {
                    helper3(root.left, res);
                }
                res.add(root.val);
                helper3(root.right, res);
            }
        }

        public List<Integer> inorderTraversal4(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper4(root, res);
            return res;
        }

        private void helper4(TreeNode root, List<Integer> res) {
            if (null != root) {
                if (null != root.left) {
                    helper4(root.left, res);
                }
                res.add(root.val);
                if (null != root.right) {
                    helper4(root.right, res);
                }
            }
        }

        public List<Integer> inorderTraversal5(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper5(root, res);
            return res;
        }

        private void helper5(TreeNode root, List<Integer> res) {
            if (null != root) {
                if (null != root.left) {
                    helper5(root.left, res);
                }
                res.add(root.val);
                if (null != root.right) {
                    helper5(root.right, res);
                }
            }
        }
    }


}
